import java.util.*;

/**
 * @author 
 * Yannic Remmet			196983
 * Tobias Trabelsi			197112
 * Anna-Katharina Wickert	197122
 */
public class BinarytreeExample {

	public static void main(String[] args) {
		Integer[] elements = new Integer[] {20, 5, 11, 10, 14, 17, 25, 22, 27, 30 };
		SearchTree<Integer> tree = new SearchTree<Integer>()	;
		
		for (int i=0; i < elements.length; i++) {
			tree.insert(elements[i]);
		}
		
		// Read in inorder traversal in an Array.
		if (test)
			System.out.println("tree inOrder: " + tree.inOrder());
		ArrayList<TreeNode<Integer>> inOrder = new ArrayList<TreeNode<Integer>>();
		
		inOrder = tree.inOrderList();
		if (test) {
				System.out.print("inOrder: " + inOrder.toString() );
				System.out.println();
		}
		SearchTree<Integer> result = new SearchTree<Integer>();
	
		reOrgL(inOrder, 0, inOrder.size() -1, result);
		System.out.println("levelOrder: " + result.levelOrder());
		/*//Spliting
		int p = inOrder.length/2;
		String[] l = new String[p-1];
		String[] r = new String[(inOrder.length%2 == 0)? p-1 : p];
		split(l, tree);
		split(r, tree);
		System.out.println(tree.inOrder()); 
		// Read in inorder traversal in an Array.
		if (test)
			System.out.println("tree inOrder: " + tree.inOrder());
		ArrayList<TreeNode<Integer>> inOrder = new ArrayList<TreeNode<Integer>>();
		
		inOrder = tree.inOrderList();
		if (test) {
				System.out.print("inOrder: " + inOrder.toString() );
				System.out.println();
		}
		SearchTree<Integer> result = new SearchTree<Integer>();
	
		reOrg(inOrder, 0, inOrder.size() -1, result);
		System.out.println("levelOrder: " + result.levelOrder()); */
		

	}

	private static <T extends Comparable<T>> void reOrgL(ArrayList<TreeNode<T>> a, int left, int right, SearchTree<T> t){
		if (left < right){
			int i = a.indexOf(splitL(a, left, right));
			t.insert(a.get(i));
			reOrgL(a, left, i-1, t);
			reOrgL(a, i+1, right, t);
			if (test)
				System.out.println("i: " + i + " a.get(i) " + a.get(i));
		}
		if (left == right){
			t.insert(a.get(left));
		}
	}
	
	private static <T extends Comparable<T>> TreeNode<T> splitL(ArrayList<TreeNode<T>> a, int left, int right) {
		if (test)
			System.out.println("left: " + left + " right: " + right);
		if (right-left >= 1){
			int middle = (right - left )/2;
			if (test)
				System.out.println("middle: "  +middle);
			return a.get(left + middle);
		}
		return a.get(0);
	}
	
	static boolean test = true;
	
}
